"""
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
"""

#暴力枚举方法：通过两个循环，双向指针找，时间复杂度高

#中心扩展法：以每个可能的中心为起点向两侧扩展
def longestPalindrome(s):
    n = len(s)
    if n <= 1:
        return s
    start = 0
    end = 0

    def expand_around_center(left, right):
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1
        #因为出循环的时候已经多移动一步了，所以有效长度需要-1
        return right - left - 1

    for i in range(n):
        odd_len = expand_around_center(i, i)
        even_len = expand_around_center(i, i+1)
        max_len = max(odd_len, even_len)
        if max_len > end - start:
            #适配偶数，对齐左边界，所以需要-1
            start = i - (max_len - 1) //2
            end = i + max_len // 2
    #+1是因为字符串切片是左闭右开区间，所以需要+1
    return s[start:end + 1]

#动态规划算法
"""
1. dp数组的定义，以及下标的含义
2. 递推公式
3. dp数组如何初始化
4. 遍历顺序
5. 打印dp数组
"""




if __name__ == '__main__':
    s = "babad"
    print(longestPalindrome(s))